package daimasuixiangmu.btree;

import java.util.ArrayList;
import java.util.List;

/**
 * TODO
 * 二叉树前序便利
 * @author gaojiaxing
 * @version 1.0.0
 * @since 2021/05/26 09:26
 */
public class DiGuiBianLi {

  /**
   * 递归法 前序便利
   * @param node
   * @param traversalList
   */
  public static void traversal(TreeNode node, List<Integer> traversalList){
    if (node == null) {
      return;
    }
    traversalList.add(node.getVal());
    traversal(node.getLeft(),traversalList);
    traversal(node.getRight(),traversalList);
  }

  /**
   * 递归法 中序便利。得出的值 从小到大排列
   * @param node
   * @param traversalList
   */
  public static void traversal1(TreeNode node, List<Integer> traversalList){
    if (node == null) {
      return;
    }
    traversal1(node.getLeft(),traversalList);
    traversalList.add(node.getVal());
    traversal1(node.getRight(),traversalList);
  }

  /**
   * 递归法 后序便利
   * @param node
   * @param traversalList
   */
  public static void traversal2(TreeNode node, List<Integer> traversalList){
    if (node == null) {
      return;
    }
    traversal2(node.getLeft(),traversalList);
    traversal2(node.getRight(),traversalList);
    traversalList.add(node.getVal());
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(null,null,5);
    root.add(1);
    root.add(7);
    root.add(8);
    root.add(6);
    root.add(3);
    root.add(2);
    /**
     *         5
     *      /    \
     *     1     7
     *      \   / \
     *      3  6  8
     *     /
     *    2
     */
    List<Integer> rst = new ArrayList<>();
    traversal(root,rst);
    // 5 1 3 2 7 6 8
    System.out.println(rst);

    rst = new ArrayList<>();
    traversal1(root,rst);
    // 1 2 3 5 6 7 8
    System.out.println(rst);

    rst = new ArrayList<>();
    traversal2(root,rst);
    // 2 3 1 6 8 7 5
    System.out.println(rst);
  }

}
